package org.example.chessboard.util;

import org.example.chessboard.model.Point;

import java.util.*;

public class ChessboardPathFinder {
    private int[][] board;  // 棋盘数据：0=空格(可通行)，1=障碍物(不可通行)
    private int rows;       // 行数
    private int cols;       // 列数

    // 四方向移动：上、右、下、左
    //private static final int[][] DIRECTIONS = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    // 八方向移动：上、右上、右、右下、下、左下、左、左上
    private static final int[][] DIRECTIONS = {
            {-1, 0},   // 上
            {-1, 1},   // 右上
            {0, 1},    // 右
            {1, 1},    // 右下
            {1, 0},    // 下
            {1, -1},   // 左下
            {0, -1},   // 左
            {-1, -1}   // 左上
    };

    public ChessboardPathFinder(int[][] board) {
        this.board = board;
        this.rows = board.length;
        this.cols = board[0].length;
    }

    /**
     * 查找两点间的最优(最短)路径
     * @param start 起点
     * @param end 终点
     * @return 路径列表（从起点到终点），无路径则返回空列表
     */
    public List<Point> findShortestPath(Point start, Point end) {
        // 检查起点和终点合法性
        if (!isValidPoint(start) || !isValidPoint(end)) {
            return Collections.emptyList();
        }

        // BFS队列
        Queue<Point> queue = new LinkedList<>();
        // 记录访问过的节点
        Set<Point> visited = new HashSet<>();
        // 记录前驱节点，用于回溯路径
        Map<Point, Point> predecessor = new HashMap<>();

        queue.add(start);
        visited.add(start);
        predecessor.put(start, null);
        boolean found = false;

        while (!queue.isEmpty() && !found) {
            Point current = queue.poll();

            // 遍历四个方向
            for (int[] dir : DIRECTIONS) {
                int newX = current.getX() + dir[0];
                int newY = current.getY() + dir[1];
                Point next = new Point(newX, newY);

                // 若未访问且是有效点
                if (isValidPoint(next) && !visited.contains(next)) {
                    queue.add(next);
                    visited.add(next);
                    predecessor.put(next, current);

                    // 找到终点
                    if (next.equals(end)) {
                        found = true;
                        break;
                    }
                }
            }
        }

        // 回溯路径
        return reconstructPath(predecessor, start, end);
    }

    /**
     * 查找指定目标点最近的空格(可通行)
     * @param target 目标点
     * @return 最近的空格坐标，无空格则返回null
     */
    public Point findNearestEmpty(Point target) {
        // 检查目标点是否在棋盘内
        if (target.getX() < 0 || target.getX() >= rows ||
                target.getY() < 0 || target.getY() >= cols) {
            return null;
        }

        // 若目标点本身就是空格，直接返回
        if (board[target.getX()][target.getY()] == 0) {
            return target;
        }

        // BFS查找最近空格
        Queue<Point> queue = new LinkedList<>();
        Set<Point> visited = new HashSet<>();

        queue.add(target);
        visited.add(target);

        while (!queue.isEmpty()) {
            Point current = queue.poll();

            // 遍历四个方向
            for (int[] dir : DIRECTIONS) {
                int newX = current.getX() + dir[0];
                int newY = current.getY() + dir[1];
                Point next = new Point(newX, newY);

                // 检查是否在棋盘内且未访问
                if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && !visited.contains(next)) {
                    visited.add(next);
                    // 找到空格
                    if (board[newX][newY] == 0) {
                        return next;
                    }
                    queue.add(next);
                }
            }
        }

        // 无可达空格
        return null;
    }

    /**
     * 检查坐标是否为有效可通行点
     */
    private boolean isValidPoint(Point p) {
        int x = p.getX();
        int y = p.getY();
        // 坐标在棋盘内且为空格(0)
        return x >= 0 && x < rows && y >= 0 && y < cols && board[x][y] == 0;
    }

    /**
     * 从前驱记录中重建路径
     */
    private List<Point> reconstructPath(Map<Point, Point> predecessor, Point start, Point end) {
        List<Point> path = new LinkedList<>();
        Point current = end;

        // 回溯到起点
        while (current != null) {
            path.add(current);
            current = predecessor.get(current);
        }

        // 若路径起点不是start，说明无有效路径
        if (path.isEmpty() || !path.get(path.size() - 1).equals(start)) {
            return Collections.emptyList();
        }

        // 反转路径（从start到end）
        Collections.reverse(path);
        return path;
    }
}
